买卖股票的最佳时期[初级算法]
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
1 2 3 4
| 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
|
示例 2:
1 2 3 4 5
| 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
|
示例 3:
1 2 3
| 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
|
官方解法
方法一:暴力法
这种情况下,我们只需要计算与所有可能的交易组合相对应的利润,并找出它们中的最大利润。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public int maxProfit(int[] prices) { return calculate(prices, 0); } public int calculate(int prices[], int s) { if (s >= prices.length) return 0; int max = 0; for (int start = s; start < prices.length; start++) { int maxprofit = 0; for (int i = start + 1; i < prices.length; i++) { if (prices[start] < prices[i]) { int profit = calculate(prices, i + 1) + prices[i] - prices[start]; if (profit > maxprofit) maxprofit = profit; } } if (maxprofit > max) max = maxprofit; } class Solution { public int maxProfit(int[] prices) { return calculate(prices, 0); } public int calculate(int prices[], int s) { if (s >= prices.length) return 0; int max = 0; for (int start = s; start < prices.length; start++) { int maxprofit = 0; for (int i = start + 1; i < prices.length; i++) { if (prices[start] < prices[i]) { int profit = calculate(prices, i + 1) + prices[i] - prices[start]; if (profit > maxprofit) maxprofit = profit; } } if (maxprofit > max) max = maxprofit; } return max; } }
|
方法二:峰谷法

这个方法的意思呢就是,我们总是在谷点买入,在峰点卖出,这样可以获得利润的最大化。所以整个程序将就是在寻找峰值和谷值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int maxProfit(int[] prices) { int i = 0; int valley = prices[0]; int peak = prices[0]; int maxprofit = 0; while (i < prices.length - 1) { while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++; valley = prices[i]; while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++; peak = prices[i]; maxprofit += peak - valley; } class Solution { public int maxProfit(int[] prices) { int i = 0; int valley = prices[0]; int peak = prices[0]; int maxprofit = 0; while (i < prices.length - 1) { while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++; valley = prices[i]; while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++; peak = prices[i]; maxprofit += peak - valley; } return maxprofit; } }
|
方法三:简单的一次遍历
这个方法也很好理解,就是如果后一个数比前一个数大,那么我们就可以尽可能的获得其中的利润。在A处买入,B处值比A大,抛出获得(B-A)的利润,C处值比B大,所以B处买入C处抛出,以此类推,直到D点,分段卖卖的利润和谷买峰卖的利润是相同的,从而避免了峰值和谷值的循环查找。而且代码也很简洁。
这应该是全场最优的解法了。执行用时: 1 ms, 在Best Time to Buy and Sell Stock II的Java提交中击败了100.00% 的用户
1 2 3 4 5 6 7 8 9 10
| class Solution { public int maxProfit(int[] prices) { int maxprofit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) maxprofit += prices[i] - prices[i - 1]; } class Solution { public int maxProfit(int[] prices) { int maxprofit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) maxprofit += prices[i] - prices[i - 1]; } return maxprofit; } }
|
原文链接:https://blog.csdn.net/qq_27480345/article/details/86490478